#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
#include<stack>
using namespace std;


//  Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        vector<vector<int>> result;
        if(root==NULL){
            return result;
        }
        queue<TreeNode*> Q;
        Q.push(root);
        int index = 0;
        int size = 1;
        while(!Q.empty()){
            stack<int> S;
            vector<int> V;
            for(int i = 0;i<size;++i){
                TreeNode* temp = Q.front();
                Q.pop();
                if(temp->left!=NULL){
                    Q.push(temp->left);
                }
                if(temp->right!=NULL){
                    Q.push(temp->right); 
                }
                if(index%2==0){
                    V.push_back(temp->val);
                }
                else{
                    S.push(temp->val);
                }
            }
            if(index%2!=0){
                while(!S.empty()){
                    V.push_back(S.top());
                    S.pop();
                }
            }
            ++index;
            size = Q.size();
            result.push_back(V);
        }
        return result;
        
    }
};


int main(){
    Solution S;
    TreeNode* root= new TreeNode(3);
    root->left = new TreeNode(9);
    root->right = new TreeNode(20);
    root->right->left = new TreeNode(15);
    root->right->right = new TreeNode(7);
    vector<vector<int>>result = S.zigzagLevelOrder(root);
    return 0;
}